(define (flatmap proc seq)
    (define (accumulate op initial sequence)
        (if (null? sequence)
            initial
            (op 
                (car sequence)
                (accumulate op initial (cdr sequence))
            )
        )
    )
    (accumulate append `() (map proc seq))
)

(define (enumerate-interval low height)
    (if (> low height)
        `()
        (cons low (enumerate-interval (+ low 1) height))
    )
)

(define (position-row position)
    (car position)
)

(define (position-col position)
    (cdr position)
)

(define (safe? col positions)
    (let (
            (kth-queen (list-ref positions (- col 1)))
            (other-queens 
                (filter 
                    (lambda (q)
                        (not (= col (position-col q)))
                    )
                    positions
                )
            )
        )
        (define (attacks? q1 q2)
            (or (= (position-row q1) (position-row q2))
                (= 
                    (abs (- (position-row q1) (position-row q2)))
                    (abs (- (position-col q1) (position-col q2)))
                )
            )
        )
        (define (iter q board)
            (or (null? board)
                (and 
                    (not (attacks? q (car board)))
                    (iter q (cdr board))
                )
            )
        )
        (iter kth-queen other-queens)
    )
)


(define (adjoin-position row col rest-of-queens)
    (append rest-of-queens (list (cons row col)))
)

(define (queens  board-size)
    (define empty-board
        `()
    )
    (define (queens-cols k)
        (if (= k 0)
            (list empty-board)
            (filter
                (lambda (positions) 
                    (safe? k positions)
                )
                (flatmap
                    (lambda (rest-of-queens) 
                        (map
                            (lambda (new-row) 
                                (adjoin-position new-row k rest-of-queens)
                            )
                            (enumerate-interval 1 board-size) 
                        )
                    )
                    (queens-cols (- k 1))
                )
            )
        )        
    )
    (queens-cols board-size)
)
(display (queens 8))
(exit)